package com.shuang.tree37;

public class IsValidBST {
    //二叉搜索树中序遍历时 每次得到的节点的值 肯定是递增的 并且不能出现重复的数
    //使用递归 中序 （可以定义一个数组 每次将 中的取值放到数组中 在判断数组是不是递增的）
    //可以不用定义数组 直接递归实现 定义一个全局变量

    //定义一个全局变量 用于记录上一个节点
    TreeNode preNode;
    public boolean isValidBST(TreeNode root) {

        // 终止条件
        if (root == null){
            return true;
        }

        //左
        boolean left = isValidBST(root.left);
        //左子树判断如果不是搜索树 直接返回
        if (!left){
            return false;
        }

        //中 判断当前节点和上一个节点的值 如果当前节点小于等于上一个节点的值 则返回false
        if (preNode != null && root.val <= preNode.val){
            return false;
        }

        //如果满足 当前节点的值大于前一个节点 则记录当前节点
        preNode = root;

        //右
        boolean right = isValidBST(root.right);
        //最后 判断右子树是否满足搜索二叉树条件
        return right;
    }
}
